/*
题目：数据流中的中位数
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：
    void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    double findMedian() - 返回目前所有元素的中位数。

https://leetcode.cn/problems/find-median-from-data-stream
 */
class MedianFinder {
    int nums;
    PriorityQueue<Integer> heapMax = null;
    PriorityQueue<Integer> heapMin = null;

    public MedianFinder() {
        heapMax = new PriorityQueue<> (new HeapComparator());//存储小于中位数的值
        heapMin = new PriorityQueue<> ();//存储大于中位数的值

        nums = 0; //表示当前元素个数
    }
    
    public void addNum(int num) {
        if ((nums & 1) == 0) {  //如果当前元素个数是偶数
            heapMin.offer(num);  //先存入小根堆，然后取出堆顶元素存入大根堆
            heapMax.offer(heapMin.poll());
        } else {  //如果当前元素个数是奇数
            heapMax.offer(num);
            heapMin.offer(heapMax.poll());
        }

        nums++;
    }
    
    public double findMedian() {
        if ((nums & 1) == 1) {  //如果当前元素个数是奇数
            return heapMax.peek();
        }
        return (heapMax.peek() + heapMin.peek()) / 2.0;
    }
}

class HeapComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}